package com.zjsru.plan2023.oneday;

/**
 * @Author: cookLee
 * @Date: 2023-11-06
 *  最大单词长度乘积
 */
public class MaxProduct {

    /**
     * 主
     * \
     * 输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
     * 输出：16
     * 解释：这两个单词为 "abcw", "xtfn"。
     * \
     * 输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
     * 输出：4
     * 解释：这两个单词为 "ab", "cd"。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MaxProduct maxProduct = new MaxProduct();
        String[] words = new  String[]{"abcw","baz","foo","bar","xtfn","abcdef"};
        System.out.println(maxProduct.maxProduct(words));
    }

    /**
     * 最大产品:位运算模拟
     *
     * @param words 单词
     * @return int
     */
    public int maxProduct(String[] words) {
        int idx = 0;
        //构建一个存放每个字符串中是否有重复字母出现过的int数组
        int[] flag = new int[words.length];
        for (String word : words) {
            //位合集
            int letterSum = 0;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                int number = c - 'a';
                //位运算，字符映射为一个小写字母的位置（0到25），如果其中一个位为1，结果位也为1。如果两个位都为0，结果位为0。
                //映射后的number代表字母的ascii码，转化为二进制，再由二进制进行异或，标记字符串中出现的字母
                letterSum |= (1 << number);
            }
            flag[idx] = letterSum;
            idx++;
        }
        int ans = 0;
        //双循环遍历找出答案
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < i; j++) {
                //按位与 & 的结果为 0，表示两个字符串没有共同的字母，结果为 0
                if ((flag[i] & flag[j]) == 0) {
                    ans = Math.max(ans, words[i].length() * words[j].length());
                }
            }
        }
        return ans;
    }

}
